# https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/description/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def __init__(self):
        self.nodeCount = -1  # 节点名
        self.begin = 0  # 开始位置

    def amountOfTime(self, root: TreeNode, start: int) -> int:
        if root is None:
            return 0
        # 二叉树转邻接表图
        adjacencyList: list[list[int]] = []

        def preOrder(node: TreeNode, father: int) -> None:
            # 递归出口
            if node is None:
                return

            # 访问
            self.nodeCount += 1
            nodeName = self.nodeCount
            adjacencyList.append([])
            if father != -1:    # 连接
                adjacencyList[father].append(nodeName)
                adjacencyList[nodeName].append(father)
            if node.val == start:   # 记录开始位置
                self.begin = nodeName

            # 下一层
            preOrder(node.left, nodeName)
            preOrder(node.right, nodeName)

            return

        preOrder(root, -1)

        # dfs找最深
        def dfs(node: int, father: int) -> int:
            deep: int = 1
            for nextNode in adjacencyList[node]:
                # 不回头
                if nextNode == father:
                    continue
                # 下一层
                deep = max(deep, dfs(nextNode, node))
            return deep + 1

        return dfs(self.begin, -1) - 1
